1875D - Jellyfish and Mex - CodeForces Solution

#include <bits/stdc++.h>
#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
/// Macros
#define int long long
#define ll long long
#define sz size
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define ii pair<int, int>
#define iii pair<int, ii>
#define vii vector<ii>
#define F first
#define S second
#define T second.second
#define pb push_back
#define fl '\n'
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define IOS                           \
    ios_base::sync_with_stdio(false); \
    cin.tie(nullptr);                 \
    cout.tie(nullptr);
/// Functions
#define random() __builtin_ia32_rdtsc()
#define lgx(x, n) (log(n) / log(x))
#define lg2(x) 31 - __builtin_clz(x)
#define lg2ll(x) 63 - __builtin_clzll(x)
#define log2(x) __lg(x)
#define pi acos(-1)
/// Red-Black Tree Template
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
//  using namespace __gnu_pbds;
//  typedef tree < long long ,  null_type ,  less<long long> ,  rb_tree_tag ,  tree_order_statistics_node_update > ordered_set;
// #define less_than(n) order_of_key(n)
// #define en_pos(n) find_by_order(n)
/// Prime numbers  173,179,311,331,737,1009,2011,2027,3079,4001,100003
///===================================================================
/// Quick Pow
// ull qpow(ull x, ull e){
//	if(!e) return 1;
//	if(e&1) return (qpow(x , e-1)*x) % MOD;
//	return qpow((x*x) % MOD , e>>1) % MOD;
// }
/// Criba de factores primos
// void Criba(int n){
//     fact[2]=2;
//     for(int i=2; i<n; i+=2) fact[i]=2;
//     for(int i=3; i<n; i+=2){
//         if(fact[i]==inf){
//             fact[i]=i;
//             for(int j=i*i; j<n; j+=i+i) fact[j]=min(fact[j], i);
//         }
//     }
// }
/// Sacar los factores primos en O(factores)
// fill(fact, fact+mxn, inf);
// Criba(mxn);
// while(num!=1){
//     if(fact[num]==di) vec[vec.sz()-1].scd++;
//     else vec.push_back({fact[num], 1});
//     di=fact[num];
//     num/=fact[num];
// }
// for(auto i:vec){
//     sum+=(qpow(i.fst, i.scd+1)-1)/(i.fst-1);
// }
using namespace std;

const int mxn = 3e5 + 1, INF = 1e18, mod = 998244353;

int n, last, ans, mex, ar[mxn], dp[mxn];
map<int, int> mp;

void Solve()
{
    cin >> n;

    mp.clear();
    for (int i = 1; i <= n; i++)
    {
        cin >> ar[i];
        if (ar[i] < n)
        {
            mp[ar[i]]++;
        }
    }

    last = -1;
    mex = -1;
    for (auto i : mp)
    {
        if (i.F - last > 1)
        {
            mex = last + 1;
            break;
        }
        else
            last = i.F;
    }
    if (mex == -1)
        mex = last + 1;

    if (mex == 0)
    {
        cout << mex << '\n';
        return;
    }

    for (int i = 0; i < mex; i++)
        dp[i] = INF;
    dp[mex] = 0;
    for (int i = mex; i > 0; i--)
    {
        for (int j = i - 1; j >= 0; j--)
        {
            dp[j] = min(dp[j], dp[i] + (mp[j] - 1) * i + j);
        }
        /* for(int j = 0; j<=mex; j++) cout<<dp[j]<<" ";
        cout<<'\n'; */
    }

    cout << dp[0] << '\n';
}

int32_t main()
{
    IOS;

    cout.setf(ios::fixed);
    cout.precision(0);

    int tc = 1;
    cin >> tc;
    for (int i = 1; i <= tc; i++)
    {
        Solve();
    }

    return 0;
}